/*
https://leetcode-cn.com/problems/find-the-minimum-number-of-fibonacci-numbers-whose-sum-is-k/solution/he-wei-k-de-zui-shao-fei-bo-na-qi-shu-zi-shu-mu-by/
 */
import java.util.ArrayList;
import java.util.List;

public class Solution1414 {
    public int findMinFibonacciNumbers(int k) {
        List<Integer> list=new ArrayList<>();
        list.add(1);
        int a=1,b=1;
        while (a+b<=k){
            int c=a+b;
            list.add(c);
            a=b;
            b=c;
        }
        int ans=0;
        for (int i=list.size()-1;i>=0 & k>0;i--){
            if (k-list.get(i)>=0){
                k=k-list.get(i);
                ans++;
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(new Solution1414().findMinFibonacciNumbers(7));
    }
}
